package pers.tz.题目.leetcode;

/**
 * @author irony
 * @date 2024-03-11
 */
public class leetcode_0036_有效的数独 {
//请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
//
// 数字 1-9 在每一行只能出现一次。
// 数字 1-9 在每一列只能出现一次。
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
//
// 注意：
// 一个有效的数独（部分已被填充）不一定是可解的。
// 只需要根据以上规则，验证已经填入的数字是否有效即可。
// 空白格用 '.' 表示。
//
// 示例 1：
//输入：board =
//[['5','3','.','.','7','.','.','.','.']
//,['6','.','.','1','9','5','.','.','.']
//,['.','9','8','.','.','.','.','6','.']
//,['8','.','.','.','6','.','.','.','3']
//,['4','.','.','8','.','3','.','.','1']
//,['7','.','.','.','2','.','.','.','6']
//,['.','6','.','.','.','.','2','8','.']
//,['.','.','.','4','1','9','.','.','5']
//,['.','.','.','.','8','.','.','7','9']]
//输出：true
//
// 示例 2：
//输入：board =
//[['8','3','.','.','7','.','.','.','.']
//,['6','.','.','1','9','5','.','.','.']
//,['.','9','8','.','.','.','.','6','.']
//,['8','.','.','.','6','.','.','.','3']
//,['4','.','.','8','.','3','.','.','1']
//,['7','.','.','.','2','.','.','.','6']
//,['.','6','.','.','.','.','2','8','.']
//,['.','.','.','4','1','9','.','.','5']
//,['.','.','.','.','8','.','.','7','9']]
//输出：false
//解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无
//效的。
//
// 提示：
// board.length == 9
// board[i].length == 9
// board[i][j] 是一位数字（1-9）或者 '.'

    public static void main(String[] args) {
        char[][] board = new char[][] {
                {'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}
        };
        System.out.println(isValidSudoku(board));
    }

    public static boolean isValidSudoku(char[][] board) {
        // 标记第N行、列、桶的数字是否存在
        boolean[][] row = new boolean[9][9]; // 9行
        boolean[][] column = new boolean[9][9]; // 9列
        boolean[][] bucket = new boolean[3][9]; // 9个桶

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] != '.') {

                    // 桶编号
                    int bucketId = i / 3 + j / 3;

                    int num = board[i][j] - '0';
                    // 第i行、第i列、第N个桶，是否又出现了该数字
                    if (row[i][num - 1] || column[i][num - 1] || bucket[bucketId][num - 1]) {
                        return false;
                    }

                    // 记录该数字出现过
                    row[i][num - 1] = true;
                    column[i][num - 1] = true;
                    bucket[bucketId][num - 1] = true;
                }
            }
        }

        return true;
    }
}
